package 单调栈;

import java.lang.reflect.Array;
import java.util.*;

/**
 * TODO
 *
 * @Description
 * @Author Lx
 * @Date 2024/7/28 21:36
 **/
public class 单调栈3_下一个更大的元素II {
    public int[] nextGreaterElements(int[] nums) {
        //同样也是维护一个降序的下标队列，但是题目要求是循环的，我们就给边界进行一下控制，当到了nums.length之后就回到0，只需要模nums.length即可

        //以前只需要顾右边，现在他可能会出现在自己循环一遍之后，在自己的左边

        //思路1:暴力，可以直接空间换时间，我们把数组给copy一份加到自己后面
        //1.构造数组
        int[] doubleNums = new int[nums.length*2];
        Arrays.fill(doubleNums, -1);
        int len=0;
        for(int i=0;i<2;i++){
            for (int j = 0; j < nums.length; j++) {
                doubleNums[len++]=nums[j];
            }
        }

//        System.out.println("doubleNums"+Arrays.toString(doubleNums));
        int[] res = new int[nums.length];
        Arrays.fill(res,-1);
        Deque<Integer> st = new LinkedList<>();
        //2.正常的像每日温度的那个单调栈一样
        //维护一个降序的st
        for (int i = 0; i < doubleNums.length; i++) {
            if(!st.isEmpty()&& doubleNums[st.peek()]<doubleNums[i]){
//                System.out.println("当前元素："+doubleNums[i]);
                //出栈
                while(!st.isEmpty()&& doubleNums[st.peek()]<doubleNums[i]){
                    int index=st.pop();//拿到下标
//                    System.out.println("出栈下标："+index+"----出栈元素："+doubleNums[index]);

                    int value = doubleNums[index];

                    if(res[index%nums.length]<value){
//                        System.out.println("res"+index%nums.length+": "+res[index%nums.length]+"---->"+value);
                        res[index%nums.length]=doubleNums[i];
                    }
                }
                st.push(i);
            }else{
                //入栈
                st.push(i);
            }
        }

        return res;
    }

    public static void main(String[] args) {
//        Scanner sc =new Scanner(System.in);
//        String input = sc.nextLine();
//        System.out.println(input);
        int[] nums={1,2,1};
        int[] res = new 单调栈3_下一个更大的元素II().nextGreaterElements(nums);
        System.out.println(Arrays.toString(res));
    }
}
